package 背包问题;

public class 背包问题_完全背包 {
/**
 * 多重背包：物品数量有限制
 * 0—1背包：dp[ i ][ j ] = max ( dp[ i-1 ][ j ], dp[ i-1 ][ j - ci ] + wi )；
	完全背包：dp[ i][ j ] = max ( dp[ i-1 ][ j ], dp[ i ][ j - ci ] + wi )；
 * */
	
	  public static int completePack(int V,int N,int[] weight,int[] value){
	        //初始化动态规划数组
	        int[][] dp = new int[N+1][V+1];
	        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
	        for(int i=1;i<N+1;i++){
	            for(int j=1;j<V+1;j++){
	                //如果第i件物品的重量大于背包容量j,则不装入背包
	                //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
	                if(weight[i-1] > j)
	                    dp[i][j] = dp[i-1][j];
	                else
	                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i-1]]+value[i-1]);
	            }
	        }
	        return dp[N][V];
	        //则容量为V的背包能够装入物品的最大值为
	       /* int maxValue = dp[N][V];
	        int j=V;
	        String numStr="";
	        for(int i=N;i>0;i--){
	            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
	            while(dp[i][j]>dp[i-1][j]){
	                numStr = i+" "+numStr;
	                j=j-weight[i-1];
	            }
	            if(j==0)
	                break;
	        }
	        return numStr;*/
	    }
}
	
